package someTestExcemple.huaweiOd.container.tree.dijkstraOrFloyd;
//华为OD机试 - 电脑病毒感染 - Dijkstra算法（Java 2024 D卷 200分）
//https://blog.csdn.net/guorui_java/article/details/138415920
import java.util.*;

/*这是一个经典的图中的单源最短路径问题，
        其中节点是电脑，边是电脑间的连接，边的权重是感染时间。
        可以使用 Dijkstra 算法来解决这个问题，找出从源节点（初始感染的电脑）到所有其他节点的最短路径。
        此外，我们需要考虑图可能是不连通的情况，如果存在某些节点不可达，则应返回 -1。*/

//Dijkstra 算法是一种用于求解带权有向图中单个源节点到所有其他节点最短路径的贪心算法。
public class ComputerVirus {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 电脑数量
        int M = scanner.nextInt();  // 连接数量

        // 使用邻接表表示图 todo 图的邻接表表示法学习一下
        List<List<Node>> graph = new ArrayList<>();
        //初始化一下
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
            //grep[0]不用，因为电脑从1开始
        }

        for (int i = 0; i < M; i++) {
            int u = scanner.nextInt(); //弧尾
            int v = scanner.nextInt(); //弧头
            int t = scanner.nextInt(); //感染时间
            graph.get(u).add(new Node(v, t));  // 添加边 u -> v
        }

        int start = scanner.nextInt();  // 最开始病毒所在电脑编号

        // 使用Dijkstra算法找到从起点到所有点的最短路径
        int[] minTime = dijkstra(graph, N, start);

        // 找到最大的最短路径时间，如果有电脑不可达，则返回-1
        int maxTime = 0;
        for (int i = 1; i <= N; i++) {
            if (minTime[i] == Integer.MAX_VALUE) {
                System.out.println(-1);
                return;
            }
            maxTime = Math.max(maxTime, minTime[i]);
        }

        System.out.println(maxTime);
    }

    // Dijkstra算法实现，使用优先队列
    private static int[] dijkstra(List<List<Node>> graph, int N, int start) {
        //初始化距离数组
        int[] dist = new int[N + 1]; //每台电脑到初始中毒电脑的最短感染时间 //0号位不用
        Arrays.fill(dist, Integer.MAX_VALUE); //先默认都不可达
        dist[start] = 0; //自己到自己的感染时间就是0

        //按感染时间升序
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.time));
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            //当前路径到达节点
            int u = current.id;
            int currentDist = current.time;

            if (currentDist > dist[u]) continue;  // 已经有更短的路径
            //遍历u号电脑可以感染的电脑，
            for (Node neighbor : graph.get(u)) {
                int v = neighbor.id;
                int t = neighbor.time;
                //找到到下一个节点v的更小的路径
                if (dist[u] + t < dist[v]) {
                    //更新感染时间
                    dist[v] = dist[u] + t;
                    pq.offer(new Node(v, dist[v]));
                }
            }
        }

        return dist;
    }

    // 辅助类表示节点及其到起点的时间
    static class Node {
        int id;  //可感染的电脑id
        int time; //感染时间

        Node(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }
}
